'''
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/?envType=study-plan-v2&envId=top-interview-150
'''
from collections import deque
from typing import List

dic = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z'],
}
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        n = len(digits)
        res = []
        path = deque()
        def dfs(i):
            if i == n:
                res.append(''.join(path))
                return
            for c in dic[digits[i]]:
                path.append(c)
                dfs(i + 1)
                path.pop()
        dfs(0)
        return res

digits = '23'
print(Solution().letterCombinations(digits))